package dynamicPrograming.钢条切割;

public class dpBottomToTop {

    public static int cut( int[] p , int n ){

        int[] r = new int[n+1];

        for( int i = 1 ; i <= n ; i++){
            int q = Integer.MIN_VALUE;
            for( int j = 1 ; j <= i ; j++){
                q = Math.max(q , p[j] + r[i-j]);
            }
            r[i] = q;
        }
        return r[n];
    }

    public static void main(String[] args) {
        int[] p = new int[]{0,1,5,8,9,10,17,17,20,24,30};
        System.out.println(cut(p,5));
    }

}
